Caos nella Catena di Approvvigionamento 📉
Le navi stanno arrivando in ordine disordinato. Dobbiamo calcolare il Metrica del Caos (numero di inversioni) per ottimizzare il controllore del traffico AI.
Che cosa è un'Inversione?
Una coppia di indici $(i, j)$ è un'inversione se:
- $i < j$ (La nave $i$ arriva prima della $j$)
- $A[i] > A[j]$ (La nave $i$ ha un ID di priorità più alto)
Analisi 🔍
Sequenza Esempio: [2, 4, 1, 3, 5]
- ❌ (2, 1): 2 arriva prima di 1, ma 2 > 1
- ❌ (4, 1): 4 arriva prima di 1, ma 4 > 1
- ❌ (4, 3): 4 arriva prima di 3, ma 4 > 3
- Caos Totale: 3 Inversioni
La Sfida
Un ciclo annidato con approccio forzato è $O(N^2)$.
per i in range(n):
per j in range(i+1, n): ...
per j in range(i+1, n): ...
Per $N=100.000$, questo richiede circa 10 miliardi di operazioni. Risultato: Tempo massimo superato.